package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

	 public List<List<Integer>> fourSum(int[] nums, int target) {
		 List<List<Integer>> result=new ArrayList<List<Integer>>();
		 if(nums.length<4)return result;
		 Arrays.sort(nums);
		 for(int i=0;i<nums.length-1;i++){
			 if (i !=0 && nums[i] == nums[i-1]) {  
	                continue;  
	            }  
			 for(int j=i+1;j<nums.length-2;j++){
				 if (j != i+1 && nums[j] == nums[j-1]) {  
		                continue;  
		            }  
				 int l=j+1;
				 int r=nums.length-1;
				 while(l<r){
					 if(nums[l]+nums[r]>target-nums[i]-nums[j]){
						 r--;
					 }else if(nums[l]+nums[r]<target-nums[i]-nums[j]){
						 l++;
					 }else{
						 List<Integer> now=new ArrayList<Integer>();
						 now.add(new Integer(nums[i]));
						 now.add(new Integer(nums[j]));
						 now.add(new Integer(nums[l]));
						 now.add(new Integer(nums[r]));
						 result.add(now);
						 l++;
						 r--;
						 while(l<r&&nums[l-1]==nums[l])l++;
						 while(l<r&&nums[r+1]==nums[r])r--;
					 }
				 }
			 }
		 }
		 return result;
	 }
	 
	 public static void main(String[] args) {
		FourSum f=new FourSum();
		System.out.println(f.fourSum(new int[]{1,0,-1,0,-2,2},0));
	}
}
